POI2008 Subdivision of Kingdom

POI2008 Subdivision of Kingdom

题目大意：

给出一个具有n个节点的无向图，将其分为两个点集S1和S2，这两个集合的点的个数一样多，使得连接它们的边最少。给出一种方案。

($ n \le 26$)

题解：

点的数目很少，我们发现哪怕把所有的方案都枚举下来，也就$ \frac {C( n, \frac n 2 )} {2}$种。当n=26时，不过才500w。

但用一般的方法，我们都要在此基础上，用O(n)的复杂度来计算当前的方案的连接边数，这样显然会TLE。

我们可以dfs，维护两个点集，并时时维护连接边数。

首先把所有点都放到S2中，并枚举一个数字，把它从S2中拿出，放到S1中。

设取出来的点为p，那么对答案的影响就是，S2中与p有边的点使答案增加，S1中与p有边的点使答案减少。

于是我们需要快速求出一个点与一个点集有多少条相连的边。

我们把一个点连出去的边用一个二进制数表示，把一个点集也用一个二进制数表示，把两个数字”&”一下，数有几个1即可。

在数1时，我一开始十分无脑，不停lowbit，暴力去求，结果居然AC了。

但其实有更好的办法，可以先预处理出每一个二进制数有几个1。

但倘若预处理26位的二进制数，显然空间不够，并且时间似乎也不够。

我们可以预处理出13位的二进制数，算一个数有几个1时分成两段算即可。

综上题目即可解。

Code：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=30;
int n,m,mi;
int sta,sta1,sta2,edge[N];
int cnt[10005];
#define lowbit(x) (x&(-x))
int cnt_one(int num){//暴力求有几个1
	int res=0;
	for(;num;num-=lowbit(num))res++;
	return res;
}
int count(int num){//分成两段，利用预处理的数组O(1)求1的个数
	int left=num>>13;
	int right=num^(left<<13);
	return cnt[left]+cnt[right];
}
void solve(int num,int pos,int ans){
	if(num==n/2){
		if(mi>ans)mi=ans,sta=sta1;
		return;
	}
	if(n-pos+1+num<n/2)return;
	for(int i=pos;i<n;i++){
		sta1|=1<<i,sta2^=1<<i;
		int del=count(sta1&edge[i]);
		int add=count(sta2&edge[i]);
		solve(num+1,i+1,ans+add-del);
		sta1^=1<<i,sta2|=1<<i;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	mi=1<<30;
	for(int i=1,a,b;i<=m;i++){
		scanf("%d%d",&a,&b);
		edge[a-1]|=1<<(b-1);
		edge[b-1]|=1<<(a-1);
	}
	for(int i=0;i<n;i++)sta2|=1<<i;
	for(int i=0;i<(1<<13);i++)cnt[i]=cnt_one(i);
	solve(0,0,0);
	bool flag=0;
	for(int i=0;i<n;i++){
		if(sta&(1<<i)){
			if(flag)printf(" %d",i+1);
			else printf("%d",i+1);
			flag=true;
		}
	}
	return 0;
}